|
In constraint satisfaction research of artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem. A constraint graph is a special case of a factor graph, which allows for the existence of free variables. ==Constraint hypergraph== The constraint hypergraph of a constraint satisfaction problem is a hypergraph in which hyper vertices correspond to the variables and the hyperedges correspond to the constraints. Two hyper vertices are in the same hyperedge if the two variables occur in the same constraint.〔 A simple way to represent the constraint hypergraph is by using a classical graph with the following properties: # Vertices correspond either to variables or to constraints, # an edge can only connect a variable-vertex to a constraint-vertex, and # there is an edge between a variable-vertex and a constraint-vertex if and only if the corresponding variable occurs in the corresponding constraint. Properties 1 and 2 define a bipartite graph. The definition of the hypergraph is obtained by defining the hypervertices as the variable-vertices and the hyperedges as the sets of variable-vertices connected to each constraint-vertex. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「constraint graph」の詳細全文を読む スポンサード リンク
|